#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 30
#define INFINITY 10000
typedef struct huffuman
{
    int weight;
    char code;
    int parent, left, right;
};
//1.1.creat_huffuman
huffuman *creat_huffuman(char codes[], int weight[], int n)
{
    huffuman *box = (huffuman *)malloc(sizeof(huffuman) * (2 * n - 1));
    for (int i = 0; i < 2 * n; i++)
    {
        if (i < n)
        {
            box[i].code = codes[i];
            box[i].weight = weight[i];
        }
        else
        {
            box[i].code = ' ';
            box[i].weight = INFINITY;
        }
        box[i].parent = box[i].left = box[i].right = -1;
    }
    int min1, min2;
    int l, r;
    int visit[MAXSIZE] = {0};
    for (int j = n; j < (2 * n - 1); j++)
    {
        min1 = min2 = INFINITY;
        l = r = -1;
        for (int i = 0; i < (2 * n - 1); i++)
        {
            if (!visit[i])
            {
                if (box[i].weight < min1)
                {

                    min2 = min1;
                    min1 = box[i].weight;
                    r = l;
                    l = i;
                }
                else if (box[i].weight < min2)
                {

                    min2 = box[i].weight;
                    r = i;
                }
            }
        }
        visit[l] = visit[r] = 1;
        box[j].left = l;
        box[j].right = r;
        box[j].weight = min1 + min2;
        box[l].parent = box[r].parent = j;
    }
    return box;
}
//1_2.visit_huffuman
void visit_huffuman(huffuman *tree, int n)
{
    //code weight parent left right
    printf("\tcode\tweight\tparent\tleft\tright\n");
    for (int i = 0; i < 2 * n - 1; i++)
    {
        printf("%d\t%c\t%d\t%d\t%d\t%d\n", i, tree[i].code, tree[i].weight, tree[i].parent, tree[i].left, tree[i].right);
    }
}
//2.encode
void encode(huffuman *tree, int n)
{
    for (int i = 0; i < n; i++)
    {
        int stack[MAXSIZE]; //register parents
        int top = -1;
        int now = i;
        while (tree[now].parent != -1)
        {
            int parent = tree[now].parent;
            tree[parent].right == now ? stack[++top] = 1 : stack[++top] = 0;
            now = parent;
        }
        printf("%c:\t", tree[i].code);
        while (top >= 0)
        {
            printf("%2d", stack[top--]);
        }
        printf("\n");
    }
}
//3.inverse encode
void inverse_encode(huffuman *tree, char *code)
{
    int root = 0;
    for (; tree[root].parent != -1; root = tree[root].parent)
        ;
    int p = root;
    while (*code)
    {
        switch (*code)
        {
        case '1':
            p = tree[p].right;
            break;
        case '0':
            p = tree[p].left;
            break;
        default:
            break;
        }
        *code++;
        if (tree[p].right == -1 && tree[p].left == -1)
        {
            printf("%c", tree[p].code);
            p = root;
        }
    }
}
int main()
{
    /*******************code*******************/
    char *code = "abcdef";
    int weight[6] = {5, 32, 18, 7, 25, 13};
    int n = 6;
    huffuman *tree = creat_huffuman(code, weight, n);
    printf("/***************huffuman_tree:***************/\n");
    visit_huffuman(tree, n);
    printf("/**************huffuman_encode:**************/\n");
    encode(tree, n);
    printf("/**************inverse_encode:***************/\n");
    char *str = "10001100100101101";
    inverse_encode(tree, str);
    /******************************************/
    printf("\n\n****************************\n");
    printf("Press Enter key to continue\n");
    getchar();
    return 0;
    /******************************************/
}
